package leetcode.day_2020_2021_1_18_2021_1_24;

import java.util.Arrays;

/**
 * https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
 * 4. 寻找两个正序数组的中位数
 */
public class Leetcode0004 {

    public static void main(String[] args) {
        System.out.println(findMedianSortedArrays(new int[]{1,3}, new int[]{2}));
        System.out.println(findMedianSortedArrays(new int[]{1,2}, new int[]{3, 4}));
        System.out.println(findMedianSortedArrays(new int[]{0,0}, new int[]{0,0}));
        System.out.println(findMedianSortedArrays(new int[]{}, new int[]{1}));
        System.out.println(findMedianSortedArrays(new int[]{10001}, new int[]{10000}));
    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int l1 = nums1.length;
        int l2 = nums2.length;

        if (l1 == 0 && l2==0) {
            return 0;
        } else if (l1 == 0 && l2 != 0) {
            return nums2.length%2 == 1 ? nums2[l2/2] : (double)(nums2[l2/2 - 1] + nums2[l2/2]) / 2;
        } else if (l2 == 0 && l1 != 0) {
            return nums1.length%2 == 1 ? nums1[l1/2] : (double)(nums1[l1/2 - 1] + nums1[l1/2]) / 2;
        } else {
            int mid = (l1 + l2) / 2;
            // true:奇數， false:偶數
            boolean flag = (l1 + l2) % 2 == 1 ? true : false;
            int i = 0, j = 0, k=0;
            int[] demo = new int[l1+l2];
            while (i<l1 && j<l2) {
                if(nums1[i] < nums2[j]) {
                    demo[k++] = nums1[i++];
                } else if (nums1[i] > nums2[j]) {
                    demo[k++] = nums2[j++];
                } else {
                    demo[k++] = nums1[i++];
                    demo[k++] = nums2[j++];
                }
            }
            boolean isNums1Null = i>=l1 ? true : false;

            if (isNums1Null) {
                while (j < l2) {
                    demo[k++] = nums2[j++];
                }
            } else {
                while (i < l1) {
                    demo[k++] = nums1[i++];
                }
            }
            return flag ? demo[demo.length/2] : (double)(demo[demo.length/2 - 1] + demo[demo.length/2])/2;
        }
    }
}
